<script>
  //   给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

  //   生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

  //   来源：力扣（LeetCode）
  //   链接：https://leetcode.cn/problems/different-ways-to-add-parentheses

  //   输入：expression = "2-1-1"
  //   输出：[0,2]
  //   解释：
  //   ((2-1)-1) = 0
  //   (2-(1-1)) = 2

  /**
   * 分析
   * 根据题意理解 比如 2-1-1 把他用括号 包住 有几种情况 这几种情况的返回的答案是什么
   * 两种情况
   * 2-(1-1) = 0
   * (2-1)-1 = 2
   * 所以 给 2-1-1 返回 [0,2]  但是 顺序不用管
   * 使用分治 把问题 拆分为 子问题
   * 设置 left左算子 right右算子  result存放结果的容器  memo记忆优化  我们需要 根据 - * + 来做判断
   * 对于子问题 比如 2-(1-1)
   * left 设置为 2
   * right (1-1)  计算出 返回结果为 0  即right 为 0
   * 如果 expression就一个数值 我们就直接存放  result 但是 result只有为空的时候才会直接存放这一个
   * 1-1 这种情况 则需要 递归 分为 left 1 right 1 判断 + * - 即 是 -  那么我们 就提前 1-1 把结果存放进 result
   * 最后 拿到的是 left = [2] right = [0] 循环一下 2-0 就取到第一个值 为 2 了
   * 递归的是需要退出条件的 也就是 memo 存在 这个表达式 所以 在最后 set一个表达式
   *
   * 整理一下第一次结果流程怎么走的
   * char = -
   * left = 2
   * right = 1-1
   * left 递归 就一个值 返回 left [2] 
   * rigth 递归 1-1 进入 判断 -  直接拆分为 left [1] right [1] char -  循环 根据 char 为-  所以 1-1 = 0 push到result 返回[0]
   * 此时 第一次 left [2] right [0]
   * char 最开始是 - 
   * 2-0 = 2 push 到 result 结果为 [2] 存放第一次答案的值
   */
  /**
   * @param {string} expression
   * @return {number[]}
   */
  var expression = '2-1-1';
  var memo = new Map();
  var diffWaysToCompute = function (expression) {
    // 记忆优化避免重复计算
    if (memo.has(expression)) {
      return memo.get(expression);
    }
    let result = [];
    for (let i = 0; i < expression.length; i++) {
      let char = expression.charAt(i);
      // 扫描算式 expression 中的运算符
      if (char == '*' || char == '+' || char == '-') {
        // 递归 将其拆分为 子问题 substring 两个参数返回 包含的部分 一个参数 返回 排除前面的返回后面
        let left = diffWaysToCompute(expression.substring(0, i));
        console.log(left);
        let right = diffWaysToCompute(expression.substring(i + 1));
        // 通过子问题的结果，合成原问题的结果
        for (let l of left) {
          for (let r of right) {
            switch (char) {
              case '*':
                result.push(l * r);
                break;
              case '+':
                result.push(l + r);
                break;
              case '-':
                result.push(l - r);
                break;
            }
          }
        }
      }
    }
    //  如果result 为空 添加
    if (!result.length) {
      result.push(parseInt(expression));
    }
    // 将结果添加进memo
    memo.set(expression, result);
    console.log(memo);
    return result;
  };

  console.log(diffWaysToCompute(expression));
</script>
